package C012;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    static class ListNode {
        int val;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

    public static void main(String[] args) {
        // [1,4,3,2,5,2]
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(4);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(2);
        ListNode listNode5 = new ListNode(5);
        ListNode listNode6 = new ListNode(2);
//        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        listNode5.next = listNode6;


        ListNode partition = partition(listNode1, 0);
        while (partition != null) {
            System.out.println(partition.val);
            partition = partition.next;
        }
    }

    public static ListNode partition(ListNode head, int x) {
        if(null == head) {
            return null;
        }
        ListNode maxHead = null;
        ListNode maxTail = null;
        ListNode minHead = null;
        ListNode minTail = null;
        ListNode prev = null;
        while (head != null) {
            prev = head;
            if (head.val >= x) {
                if(maxHead == null) {
                    maxHead = head;
                    maxTail = maxHead;
                }else {
                    maxTail.next = head;
                    maxTail = maxTail.next;
                }
            }else {
                if(minHead == null) {
                    minHead = head;
                    minTail = minHead;
                }else {
                    minTail.next = head;
                    minTail = minTail.next;
                }
            }
            head = head.next;
            prev.next = null;
        }

        if(minTail != null) {
            minTail.next = maxHead;
        }else {
            minHead = maxHead;
        }
        return minHead;
    }
}